|
In mathematics, the vertex enumeration problem for a polytope, a polyhedral cell complex, a hyperplane arrangement, or some other object of discrete geometry, is the problem of determination of the object's vertices given some formal representation of the object. A classical example is the problem of enumeration of the vertices of a convex polytope specified by a set of linear inequalities:〔Eric W. Weisstein ''CRC Concise Encyclopedia of Mathematics,'' 2002, ISBN 1-58488-347-2, p. 3154, article "vertex enumeration"〕 : where ''A'' is an ''m''×''n'' matrix, ''x'' is an ''n''×1 column vector of variables, and ''b'' is an ''m''×1 column vector of constants. ==Computational complexity== The computational complexity of the problem is a subject of research in computer science. A 1992 article by David Avis and Komei Fukuda presents an algorithm which finds the ''v'' vertices of a polytope defined by a nondegenerate system of ''n'' inequalities in ''d'' dimensions (or, dually, the ''v'' facets of the convex hull of ''n'' points in ''d'' dimensions, where each facet contains exactly ''d'' given points) in time O(''ndv'') and space O(''nd''). The ''v'' vertices in a simple arrangement of ''n'' hyperplanes in ''d'' dimensions can be found in O(''n''2''dv'') time and O(''nd'') space complexity. The Avis–Fukuda algorithm adapted the criss-cross algorithm for oriented matroids. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Vertex enumeration problem」の詳細全文を読む スポンサード リンク
|